#include<iostream>
#include<vector>
#include<deque>

using namespace std;

class Solution{
    public:
    //out of time
    int ans1(vector<int>& nums){
        int k = nums.size();
        int len = 2 * k;
        nums.insert(nums.end(), nums.begin(), nums.end());
        nums.pop_back();
        int maxAns = nums[0];
        for(int i = 0; i != k; i++){
            int pre = 0, tempMax = nums[i];
            for(int j = i; j != k+i; j++){
                pre = max(pre + nums[j], nums[j]);
                tempMax = max(tempMax, pre);
            }
            maxAns = max(maxAns, tempMax);
        }
        return maxAns;
    }

    int ans2(vector<int>& nums){
        int n = nums.size();
        deque<pair<int, int>> q;
        int pre = nums[0], res = nums[0];
        q.push_back({0, pre});
        for (int i = 1; i < 2 * n; i++) {
            while (!q.empty() && q.front().first < i - n) {
                q.pop_front();
            }
            pre += nums[i % n];
            res = max(res, pre - q.front().second);
            while (!q.empty() && q.back().second >= pre) {
                q.pop_back();
            }
            q.push_back({i, pre});
        }
        return res;
    }
};

void test1(){
    Solution s;
    vector<int> nums = {1,-2,3,-2};

    int ret = s.ans2(nums);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<int> nums = {5,-3,5};

    int ret = s.ans2(nums);
    cout << ret << endl;
}

void test3(){
    Solution s;
    vector<int> nums = {3,-2,2,-3};

    int ret = s.ans2(nums);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}